The present invention relates to vector quantizers for low bit rate coding of time sequential signals such as speech signals and image signals.
Vector quantization is a typical method of quantizing a speech signal or like time sequential signal by dividing the signal into frames of a predetermined interval (or blocks of a predetermined area). The vector quantization has an excellent quantization property of reducing quantization distortion for the allocated number of bits. However, it requires an extremely great number of operations to search the optimum quantization output vector best expressing the quantized signal. For example, where the frame length (or vector dimension number) is 10 and the number of bits per sample is 2, 10,485,760 times of product summing operation are required for the search. Considering a speech signal of 8 KHz sampling, this value corresponds to 830.86.times.10.sup.6 times product operation per minute. This scale is far beyond the real time operation with a single chip of DSP (Digital Signal Processor) that is currently available. Accordingly, various methods have heretofore been investigated to reduce the operation scale for the vector quantization. These methods are largely grouped into a type which involves preliminary selection and/or simplification of operation, a type with specific vector quantizer structure contrivances, and a type in which the above two types are incorporated together. The type of method based on the simplification of operation has a merit that the amount of operations can be greatly reduced depending on the way of simplification. On the demerit side, however, deterioration of the properties is inevitable. It is another demerit that different evaluation standards are used at the time of the quantizer design and at the time of the search, and therefore expected quantizer properties can not be attained at the time of the design. The type of method with structural contrivance, on the other hand, has an advantage that expected quantization properties at the time of design can be attained at the time of the search. However, there is a problem that great amount of operational reduction can not be achieved unless the contrivance is well structured. The present invention pertains to the latter type method with structural contrivance.
As typical structural contrivance type method, there are multiple stage vector quantization (B. H. Juang and A. H. Gray, "Multiple Stage Vector Quantization for Speech Coding", Proc. of Intl. Conf. on Acous., Speech and Signal Proc., 1982 (Literature 1)), conjugate structure vector quantization (Moriya and Y/da, "Vector Quantization Method", Japanese Patent Laid-Open Publication No. Sho 63-285599 (Literature 2), Moriya, "Method of and Apparatus for Multiple Vector Quantization" (Lierature 3)), vector sum vector quantization (Ira A. Gerson, "Digital Speech Coder with Improved Vector Exciting Source", Japanese Patent Laid-Open Publication No. Hei 02-502135 (Literature 4)), lattice vector quantization (J. H. Conway and N.J. A. Sloane, "Fast Quantizing and Decoding Algorithms for Lattice Quantizers and Codes", IEEE Trans. Inf. Theory, Vol. IT-28, pp. 227-232, Mar. 1982 (Literature 5), R. M. Gray, "Source Coding Theory", Ch. 5.5, Kluwer Academic Publishers, 1990 (Literature 6)), and tree structure delta quantization (Taniguchi, Ohta and Kurihara, "Speech Coding System", Japanese Patent Laid-Open Publication No. Hei 4-352200 (Literature 7)). In these methods, output codevector is formed through linear operation on basis and coefficient vectors. More specifically, in the formation of output codevector for M bits from a basis vector set {e.sub.i.sup.z } and a coefficient vector set {g.sub.i.sup.z }, selecting a basis vector subset {e.sub.k.sup.i }and a coefficient vector subset {g.sub.k.sup.i }the i-th output codevector V.sup.i is expressed as ##EQU1## Using this formula (1), the prior art method noted above is expressed as follows. In the M-bit two stage vector quantization, the following formula is given for all {i,k}, where K=2. EQU {g.sub.k.sup.i =1,2, i=0, . . . ,2.sup.M -1}
In this case, {e.sub.1.sup.i } is selected from a basis vector subset B.sub.1 consisting of C.sub.1 vectors, and {e.sub.2.sup.i } is selected from a basis vector subset B.sub.2 consisting of C.sub.2 vectors. Here C.sub.1 .times.C.sub.2 =2.sup.M. In the M-bit conjugate structure vector quantization, K=2, and EQU {g.sub.k.sup.i =.+-.1, k=1, 2, i=0, . . . ,2.sup.M -1}.
In this case, e.sub.1.sup.i is selected from the basis vector subset B.sub.1 consisting of C.sub.1 vectors, while {e.sub.2.sup.i } is selected from the basis vector subset B.sub.2 consisting of C.sub.2 vectors. Here, C.sub.1 .times.C.sub.2=2.sup.M-2. In the vector sum vector quantization, under K=M and {g.sub.k.sup.i =.+-.1}, there are M type basis vector subsets each with single basis vector e.sub.k and the output codevector is formed through arithmetic operations of M type basis vector. In the lattice vector quantization, it is featured that K is an appropriate number M.sub.o and the coefficient vectors: {g.sub.k.sup.i,i=0, . . . , 2.sup.M } consist of integers. There are M.sub.o type basis vector subsets each with single basis vector e.sub.k. Finally, in the M-bit tree structure delta quantization, there are M type basis vector subsets each with 2.sup.K vectors and coefficient vector subsets each with .+-.1 for each value of K which is {K=0,1,2, . . . , M-1}, and output codevectors of ##EQU2## are formed.
When the expression of the formula (1) is used, the vector quantization of the n-th input quantization vector x.sub.n is defined as a search problem for obtaining i for minimizing the following formula (2). ##EQU3##
Considering the M-bit vector quantization, in the usual vector quantization without any structural contrivance, it is necessary to perform input vector distance calculation 2.sup.M times. In the case of the expression of the formula (1), it is just required to perform the K times distance calculation to the input vector, which is a smaller number of times than 2.sup.M, and the subsequent operation is replaced with simple arithmetic operations. Thus, it is possible to reduce the amount of operations. Further, if there are equal numbers of v.sup.i and -v.sup.i in the basis vectors, the operations concerning the inner product (v.sup.i).sup.t v.sup.i are further reduced to one half. Generally, the properties and operation amount of the vector quantization depend on the number of basis vector sets. That is, the greater the number of basis vector sets, the better are the quantization properties, but the more is the operation amount.
Further, in a method in which the output codevectors are formed in the form of a linear sum of a plurality of basis vectors, such as the conjugate structure vector quantization, vector sum vector quantization, lattice structure vector quantization, etc., the characteristic deterioration due to transmission line errors is dispersed as characteristic deterioration of each basis vector. For this reason, the method is robust to errors compared with the single stage vector quantizer, in which deterioration due to transmission line error is loaded by the single vector.
Among the prior art quantization methods noted above, the multiple stage vector quantization and conjugate structure vector quantization require stage-by-stage search or preliminary selection for simply reducing the operation amount. However, this prevents the intrinsic characteristics from being attainable. The lattice vector quantization, on the other hand, permits equal characteristics to be attained at the time of the design and at the time of the search if all the basis vectors are designed collectively. However, since the number of basis vectors is at most equal to the number of bits, the quantization characteristics are inferior compared with the case without structural contrivance or the conjugate structure quantization. In the tree structure delta quantization, the number of basis vectors is less than the number of bits, and therefore the quantization characteristic is inferior compared with the cases of the conjugate vector quantization and lattice vector quantization. Besides, there has been no reported argorithm for designing an optimum quantizer for training sample sets.